package hash;

import java.util.NoSuchElementException;

public class MyHashMap {
    //有效节点个数
    private int size;
    //实际存储元素的Node数组
    private Node[] hashtable;
    //取模数
    private int M;
    //负载因子
    private static final double LoadFactor=0.75;

    public MyHashMap(){
        //默认初始化容量
        this(16);
    }
    public MyHashMap(int init){
        //初始化容量
        this.hashtable=new Node[init];
        this.M=init;
    }

    /**
     * 对key值进行hash运算
     * @param key
     * @return
     */
    public int hash(int key){
        return Math.abs(key)%M;
    }
    /**
     * 将一堆键值对保存到哈希表中，若key存在就修改原来的键值对，返回修改前的元素
     * @param key
     * @param val
     */
    public int  add(int key,int val){
        //先对key取模,取模后的值就是索引
        int index=hash(key);
        //遍历index对应的链表，查看key值是否存在
        for (Node x=hashtable[index];x!=null;x=x.next){
            if (x.key==key){
                int oldval=x.value;
                x.value=val;
                return oldval;
            }
        }
        //此时整个链表中不包含相对应的key值，就头插到当前链表
        Node node=new Node(key,val);
        //头节点就是hashtable[index]
        node.next=hashtable[index];
        hashtable[index]=node;
        size++;
        //添加完元素后判断是否需要扩容
        if (size>=hashtable.length*LoadFactor){
            //扩容方法
            Expansion();
        }
        return val;
    }

    /**
     * 哈希表的扩容方法。默认让新数组的长度变为原来的一倍
     */
    private void Expansion() {
        //新数组长度时原来的一倍
        Node[] newHashTable=new Node[hashtable.length*2];
        //将原数组的所有元素搬移到新的数组，此时的取模值M变为了新数组长度
        this.M=newHashTable.length;
        //进行元素搬移操作
        //遍历哈希表数组
        for (int i = 0; i <hashtable.length ; i++) {
            //遍历每个小链表
            for (Node x=hashtable[i];x!=null;){
                //暂存一下下一个节点的地址
                Node next=x.next;
                //元素搬移后的索引
                int index=hash(x.key);
                //在新数组的小链表进行头插
                x.next=newHashTable[index];
                newHashTable[index]=x;
                x=next;
            }
        }
        hashtable=newHashTable;
    }

    /**
     * 判断当前key是否在表中存在
     * @param key
     * @return
     */
    public boolean containskey(int key){
        int index=hash(key);
        for (Node x=hashtable[index];x!=null;x=x.next){
            if (x.key==key){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断value是否存在
     * @param val
     * @return
     */
    public boolean containsvalue(int val){
        //全表扫描
        for (int i=0;i<hashtable.length;i++){
            for (Node x=hashtable[i];x!=null;x=x.next){
                if (x.value==val){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 判断键值对是否存在
     * @param key
     * @param val
     * @return
     */
    public boolean containskeyval(int key,int val){
        int index=hash(key);
        for (Node x=hashtable[index];x!=null;x=x.next){
            if (x.key==key&&x.value==val){
                return true;
            }
        }
        return false;
    }

    /**
     * 哈希表的删除操作
     * @param key
     * @param val
     * @return
     */
    public boolean remove(int key,int val){
        int index=hash(key);
        //判断头节点是否时待删除节点
        Node head=hashtable[index];
        if (head.key==key&&head.value==val){
            //此时头节点就是待删除的节点
            hashtable[index]=head.next;
            head=head.next=null;
            size--;
            return true;
        }
        Node prev=head;
        while (prev.next!=null){
            if (prev.next.key==key&&prev.next.value==val){
                //此时prev恰好就是待删除节点的前驱
                Node cur=prev.next;
                prev.next=cur.next;
                cur=cur.next=null;
                size--;
                return true;
            }else {
                prev=prev.next;
            }
        }
        //当前节点在哈希表中找不到
        throw new NoSuchElementException("can't find node！cannot remove!");
    }


}

class Node{
    //对key进行hash运算
    int key;
    int value;
    //下一个节点
    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
